package leetcode_1000;

import java.util.Arrays;

/**
 *@author 周杨
 *DistinctSubsequencesII_940_ 找出一个字符串里不重复的子序列
 *describe:用动态规划 还需记录每个字母最后出现的位置 AC 94%
 *2018年11月25日 下午1:20:37
 */
public class DistinctSubsequencesII_940_ {
	public static void main(String[] args) {
		DistinctSubsequencesII_940_ test=new DistinctSubsequencesII_940_();
		test.distinctSubseqII("abc");
	}
	
	public int distinctSubseqII(String S) {
        char []chars=S.toCharArray();
        final int MOD=1000000007;
        long []dp=new long[chars.length+1];
        int []pre=new int[26];//记录上一个 这个字母出现的Index
        Arrays.fill(pre, -1);
        dp[0]=1;
        for(int i=1;i<=chars.length;++i) {
        	dp[i]=dp[i-1]*2;//这个元素可以跟前面所有组合组合 所以结果翻倍
        	int diff=chars[i-1]-'a';
        	if(pre[diff]!=-1) //如果这个元素在前面出现过
        		dp[i]=(dp[i]-dp[pre[diff]-1]+MOD)%MOD;//减去之前所有的组合 因为它可以跟其重复
        	pre[diff]=i;
        }
        return (int) (dp[chars.length]-1);
    }
}
